// 二分查找 - 利用数组的 二段性 解决问题，每次可以舍弃一段数据
// 经典在 有序数组中 找一个数/找一个数的插入位置 的问题，都可以使用二分查找
// 要求时间复杂度为 O(log n) 的题目，通常使用二分查找

// 例题 5：
// 给定一个长度为 n 的整数 山脉 数组 arr ，其中的值递增到一个 峰值元素 然后递减。
// 返回峰值元素的下标。
// 你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。
//
//        示例 1：
//
//        输入：arr = [0,1,0]
//        输出：1
//        示例 2：
//
//        输入：arr = [0,2,1,0]
//        输出：1
//        示例 3：
//
//        输入：arr = [0,10,5,2]
//        输出：1
//
//
//        提示：
//
//        3 <= arr.length <= 105
//        0 <= arr[i] <= 106
//        题目数据 保证 arr 是一个山脉数组

// 解题思路：
// 本题 arr 虽然不是一个有序数组，但是也是具备二段性的，即 arr[mid] > arr[mid - 1] 或者 arr[mid] < arr[mid - 1]
// arr[mid] > arr[mid - 1]: mid 有可能就是需要找的下标，因此不能舍弃
// arr[mid] < arr[mid - 1]: mid 肯定不是需要找的下标，因此可以舍弃
// 因此，这道题是需要找数组的右中点
// 右中点：mid = left + (right - left + 1) / 2
// x <= target: left = mid;
// x > target: right = mid - 1

public class PeakIndexInMountainArray {
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int left = 0;
        int right = n - 1;
        while(left < right){
            int mid = left + (right - left + 1) / 2;
            if(arr[mid] < arr[mid - 1]) right = mid - 1;
            else left = mid;
        }
        return left;
    }
}
